#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (i == 0 || j == 0)
                {
                    int x = i, y = j;
                    vector<int> tmp;
                    while (x < m && y < n)
                    {
                        tmp.push_back(mat[x][y]);
                        x++, y++;
                    }
                    sort(tmp.begin(), tmp.end());
                    x = i, y = j;
                    int t = 0;
                    while (x < m && y < n)
                    {
                        mat[x][y] = tmp[t];
                        t++;
                        x++, y++;
                    }
                }
            }
        }
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cout << mat[i][j] << " ";
            }
            cout << endl;
        }
        return mat;
    }
};

int main()
{
    vector<vector<int>> mat = { {3,3,1,1}, {2,2,1,2}, {1,1,1,2} };
    Solution().diagonalSort(mat);
    return 0;
}

